package leetcode.D600.T524;

import java.util.List;

class Solution {
//    public String findLongestWord(String s, List<String> dictionary) {
//        int maxLen = 0;
//        String result = "";
//        Iterator<String> iterator = dictionary.iterator();
//        while(iterator.hasNext()) {
//            String x = iterator.next();
//            if(isInString(s, x)) {
//                if(x.length() > result.length()) {
//                    result = x;
//                } else if(x.length() == result.length() && x.compareTo(result) < 0) {
//                    result = x;
//                }
//            }
//        }
//        return result;
//    }
//    private boolean isInString(String a, String b) {
//        int p = 0, q = 0;
//        while(p < a.length() && q < b.length()) {
//            if(a.charAt(p) == b.charAt(q)) {
//                p++;
//                q++;
//            } else {
//                p++;
//            }
//        }
//        return q == b.length() ? true : false;
//    }

    // 二刷
    public String findLongestWord(String s, List<String> dictionary) {
        String result = "";
        for (String t : dictionary) {
            if(isInString(s, t)) {
                if(result.length() < t.length()) {
                    result = t;
                } else if (result.length() == t.length() && result.compareTo(t) > 0) {
                    result = t;
                }
            }
        }
        return result;
    }

    private boolean isInString(String s, String t) {
        int i = 0, j = 0;
        if(t.length() > s.length()) {
            return false;
        }
        while(i < s.length() && j < t.length()) {
            if(s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        return j == t.length();
    }
}